;; Longest common subsequence
;; Copyright (C) 2022  Rocks Mazama
;;
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <https://www.gnu.org/licenses/>.

(ns mazama.sequence.lcs)

(defn- longest [xs ys]
  (let [count-x (-> xs first count)
        count-y (-> ys first count)]
  (cond
    (< count-x count-y) ys
    (> count-x count-y) xs
    :else (into xs ys))))

(defn- algorithm
  []
  (def ^:private helper
    (memoize (fn [xs ys]
               (cond
                 (or (empty? xs) (empty? ys)) nil
                 (= (first xs) (first ys)) (let [sub (helper (rest xs) (rest ys))]
                                             (if sub
                                               (map #(cons (first xs) %) sub)
                                               (-> xs first list list)))
                 :else (longest (helper xs (rest ys))
                                (helper (rest xs) ys))))))
  helper)

(defn lcs
  "Return the longest common subsequences of `xs` and `ys` as a set."
  [xs ys]
  (let [result ((algorithm) xs ys)]
    (def ^:private helper nil)
    (set result)))
